#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int l[N],r[N];



void dfs1(int x)
{
		if(!x)return;
	cout << x << " ";
	if(l[x]) dfs1( l[x] );
	if(r[x]) dfs1(r[x] );
}

void dfs2(int x)
{
		if(!x)return;
	if(l[x]) dfs2( l[x] );
	cout << x << " ";
	if(r[x]) dfs2(r[x] );
}

void dfs3(int x)
{
	if(!x)return;
	 dfs3( l[x] );
	 dfs3(r[x] );
    cout << x << " ";
}
int main()
{
	int n; cin >> n;
	for(int i = 1;i <=n;i++)
	{
		cin >> l[i] >> r[i];
		
	}
	dfs1(1);
	cout << endl;
	dfs2(1);
	cout << endl;
	dfs3(1);
	cout << endl;
	
	return 0;
 } 
